package leetcode_900;

/**
 *@author 周杨
 *ProfitableSchemes_879_  有G个人 做若干任务 获取若干收益  问至少获得P利润的情况下 有多少分配方案
 *describe:动态规划 AC 30%
 *2018年11月8日 下午2:36:00
 */
public class ProfitableSchemes_879_ {
	/**
	 * describe: 三维数组 动态规划 AC 30%
	 * 2018年11月8日 下午2:17:14
	 */
	public int profitableSchemes(int G, int P, int[] group, int[] profit) {
		int MOD=1000000007;
        int dp[][][]=new int[group.length+1][P+1][G+1];//完成dp[i][j][k]  在前i个任务中 完成至少j个利润 和k个人数 的数量
        dp[0][0][0]=1;
        for(int i=1;i<=group.length;++i) {//任务
        	for(int j=0;j<=P;++j) {//利润
        		for(int k=0;k<=G;++k) {//人数
        			//k-group[i-1]=没有完成第i-1个任务的人数
        			dp[i][j][k]=((dp[i-1][j][k])//当前最优解为 遍历到以前没有做到这个任务 那么现在做了 和以前的数量是不变的
        					+(k<group[i-1]?0:dp[i-1][Math.max(0, j-profit[i-1])][k-group[i-1]]))
        					%MOD;
        		}
        	}
        }
        long res=0;
        for(int i=0;i<=G;++i)//依次累加  无论你使用多少人数 都没有关系  都是解
        	res+=dp[group.length][P][i];
        return (int) (res%MOD);
    }
}
